package com.cqs.leetcode.dp;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

/**
 * xw
 * 2022/10/3
 */
public class WildcardMatching44 {

    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= p.length() && p.charAt(i - 1) == '*'; i++) dp[i][0] = true;
        for (int i = 1; i <= p.length(); i++) {
            char cp = p.charAt(i - 1);
            for (int j = 1; j <= s.length(); j++) {
                char cs = s.charAt(j - 1);
                boolean b1 = dp[i - 1][j - 1] && (cp == cs || cp == '*' || cp == '?');
                boolean b2 = dp[i - 1][j] && cp == '*';
                boolean b3 = dp[i][j - 1] && cp == '*';
                dp[i][j] = b1 || b2 || b3;
            }
        }
        return dp[p.length()][s.length()];
    }


    public static void main(String[] args) {
        WildcardMatching44 w = new WildcardMatching44();
        List<Pair<String, String>> cases = new ArrayList<>();
        cases.add(new Pair<>("ho", "**ho"));
        cases.add(new Pair<>("", "***"));
        cases.add(new Pair<>("a", ""));
        cases.add(new Pair<>("aa", "a"));
        cases.add(new Pair<>("aa", "*"));
        cases.add(new Pair<>("aab", "*"));
        cases.add(new Pair<>("aab", "*b"));
        cases.add(new Pair<>("cb", "?"));
        cases.add(new Pair<>("cb", "?*"));
        cases.add(new Pair<>("cb", "cb*"));
        cases.add(new Pair<>("ab", "*ab"));
        cases.add(new Pair<>("aab", "a*ab"));
        cases.add(new Pair<>("aab", "*ab"));
        cases.forEach(new Consumer<Pair<String, String>>() {
            @Override
            public void accept(Pair<String, String> p) {
                System.out.println(p.getKey() + "\t" + p.getValue() + "\t" + w.isMatch(p.getKey(), p.getValue()));
            }
        });
    }
}
